# -*- coding: utf-8 -*-
# @Author: bao
# @Date:   2017-02-17 11:20:24
# @Last Modified by:   bao
# @Last Modified time: 2017-05-14 14:44:48

from gen_topo import *
from datetime import datetime

class gen_topo_fully(gen_topo):
	"""
	Non-blocking circuit switch
	"""
	def __init__(self):
		gen_topo.__init__(self)

	def _transform(self, wl_graph, tf_graph, degree, base_len):
		'''
		Generate new topology based on multi max_weight_matching (directed bipartite graph)
		node (bp_src, bipartite=0, degree=0)
		node (bp_dst, bipartite=0, degree=0)
		edge (src, dst, 'weight')
		'''
		starttime = datetime.now()
		remain_edges = []
		temp_graph = tf_graph.copy()
		while temp_graph.edges():
			match = nx.max_weight_matching(temp_graph, maxcardinality=False)
			# print len(match), match
			for src in match:
				dst = match[src]
				if src <= base_len:
					# print src, dst, temp_graph[src][dst]['weight']
					max_degree = max(wl_graph.node[src]['degree'], wl_graph.node[dst]['degree'])
					if max_degree < degree:
						traffic_weight = get_weight(temp_graph[src][dst]['weight'])
						wl_max = degree - max_degree
						wl_num = min(traffic_weight, wl_max)
						wl_graph.add_edge(src, dst, weight=wl_num)
						wl_graph.node[src]['degree'] += wl_num
						wl_graph.node[dst]['degree'] += wl_num
					else:
						remain_edges.append((src, dst))
					temp_graph.remove_edge(src, dst)
		endtime = datetime.now()
		timediff = endtime - starttime
		print '_transform time ',timediff

	def _matchings(self, graph, pre_matches, max_degree, base_len):
		'''
		Minimal Wavelength Adjustment (MWA) based on pre_matches
		Extending the algorithms from paper "WaveCube: A scalable, fault-tolerant, high-performance optical data center architecture"
		'''
		starttime = datetime.now()
		wl_graph = graph.copy()
		counter = 1
		max_d = max_degree
		match_results = {}
		remain_pre_matches = {}
		for i in pre_matches:
			max_d_nodes = [] # nodes with degree max_d in graph
			for node in wl_graph.nodes():
				if wl_graph.node[node]['degree'] == max_d:
					max_d_nodes.append(node)

			inter_nodes = []
			inter_edges = list(set(pre_matches[i]) & set(wl_graph.edges())) # common edges
			pre_remian_edges = list(set(pre_matches[i]) - set(inter_edges))
			[inter_nodes.extend([src,dst]) for (src,dst) in inter_edges]
			'''
			print '\n', "pre_matches:", i, counter, pre_matches[i]
			print len(set(pre_matches[i])&set(wl_graph.edges())), set(pre_matches[i])&set(wl_graph.edges())
			print "max_degree:", max_d, "max_d_nodes", len(max_d_nodes), max_d_nodes		
			print "inter_edges:", inter_edges
			print "pre_remian_edges:", pre_remian_edges
			'''
			if set(max_d_nodes).issubset(set(inter_nodes)): # matches i covers all nodes with max_d
				# print "case1: cover all nodes with max_degree d"
				match_results[counter] = pre_matches[i]
				self._update_graph_fully(wl_graph, match_results[counter])
				max_d -= 1
				counter += 1
			else:
				# print "case2: find a matches cover other max_degree d nodes"
				sub_match = []
				sub_graph = wl_graph.copy()
				sub_graph.remove_nodes_from(inter_nodes)
				sub_match_dict = nx.bipartite.maximum_matching(sub_graph)
				[sub_match.append((src,sub_match_dict[src])) for src in sub_match_dict if src <= base_len]

				sub_inter_nodes = []
				[sub_inter_nodes.extend([src,dst]) for (src,dst) in sub_match]

				if (set(max_d_nodes)-set(inter_nodes)).issubset(sub_inter_nodes) \
					and len(set(sub_match)&set(inter_edges)) == 0:
					#print "case3: a matches cover other max_degree d nodes !!!"
					new_match_nodes = []
					new_match = list(set(sub_match)|set(inter_edges))
					[new_match_nodes.extend([src,dst]) for (src,dst) in new_match]
					remain_nodes = list(set(wl_graph.nodes()) - set(new_match_nodes))
					remain_nodes.sort()
					#print len(new_match), new_match, remain_nodes
					if remain_nodes:
						self._augument_perfect_fully(remain_nodes, new_match, pre_matches[i], base_len)
						
					match_results[counter] = new_match
					self._update_graph_fully(wl_graph, match_results[counter])
					max_d -= 1
					counter += 1
				else:
					remain_pre_matches[i] = pre_matches[i]

		for x in range (counter, max_degree+1):
			new_match = []
			new_match_nodes = []
			match_dict = nx.bipartite.maximum_matching(wl_graph)
			[new_match.append((src,match_dict[src])) for src in match_dict if src <= base_len]
			[new_match_nodes.extend([src,dst]) for (src,dst) in new_match]
			remain_nodes = list(set(wl_graph.nodes()) - set(new_match_nodes))
			remain_nodes.sort()

			com_len = 0
			index = 0
			for i in remain_pre_matches:
				counter = 0
				for src,dst in remain_pre_matches[i]:
					if src in remain_nodes and dst in remain_nodes:
						counter += 1
				counter += len(list(set(remain_pre_matches[i]) & set(new_match)))
				if com_len < counter:
					index = i
					com_len = counter

			self._augument_perfect_fully(remain_nodes, new_match, remain_pre_matches[index], base_len)
			del remain_pre_matches[index]
			match_results[x] = new_match
			self._update_graph_fully(wl_graph, match_results[x])
		endtime = datetime.now()
		timediff = endtime - starttime
		print 'matchings time ',timediff
		return match_results
		
	def _update_graph_fully(self, graph, matches):
		'''
		Update the node 'degree' and edge 'weight' based on new mathcing
		'''
		for (src,dst) in matches:
			if (src, dst) in graph.edges():
				graph.node[src]['degree'] -= 1
				graph.node[dst]['degree'] -= 1
				if graph.edge[src][dst]['weight'] > 1:
					graph.edge[src][dst]['weight'] -= 1
				else:
					graph.remove_edge(src, dst)

	def _augument_perfect_fully(self, remain_nodes, cur_matches, pre_matches, base_len):
		'''
		Augument the cur_matches to perfect matches with pre_matches
		Maxmizing the overlap between cur_matches and pre_matches
		'''
		src_nodes = remain_nodes[:len(remain_nodes)/2]
		dst_nodes = remain_nodes[len(remain_nodes)/2:]
		remain_pre_matches = list(set(pre_matches) - set(cur_matches))
		
		#print src_nodes
		#print dst_nodes
		#print remain_pre_matches

		for src,dst in remain_pre_matches:
			if src in src_nodes and dst in dst_nodes:
				cur_matches.append((src,dst))
				src_nodes.remove(src)
				dst_nodes.remove(dst)

		for src in src_nodes:
			find = False
			for dst in dst_nodes:
				if src+base_len != dst:
					find = True
					cur_matches.append((src, dst))
					dst_nodes.remove(dst)
					break
			if find == False:
				dst = dst_nodes[0]
				src1,dst1 = cur_matches.pop()
				cur_matches.append((src1, dst))
				cur_matches.append((src, dst1))
		cur_matches.sort()